home *** CD-ROM | disk | FTP | other *** search
/ Mac Mania 6 / MacMania 6.toast / / Multimedia & Desktop / sk8 / SK8InJava / Code / Collections / ListCollection.java < prev    next >
Encoding:
Java Source  |  1997-02-27  |  7.6 KB  |  311 lines  |  [TEXT/CWIE]
  1. /*  SK8 © 1997 Apple Computer, Inc.
  2.     This code is protected under the current SK8 License
  3.     See http://sk8.research.apple.com/ for more information
  4.     Apple Research Laboratories
  5. */
  6.  
  7.  
  8. /* 
  9.     list
  10.     a linked list that adheres to the SK8 collection protocol
  11.     
  12. */
  13.  
  14.  
  15.  
  16. public class list extends collection {
  17.  
  18.     // defining protected data members
  19.     protected Object             mValue; 
  20.     protected list     mRest;
  21.     protected boolean            mIsEmpty;
  22.     
  23.     
  24.     // Defining methods
  25.  
  26.     // constructor
  27.     public list(){
  28.         mIsEmpty = true;
  29.         mValue = null;
  30.         mRest = null;
  31.     }
  32.     
  33.     // protected methods
  34.     // subclasses should override checkvisitstate, newvisitstate, & newSibling
  35.     protected void checkvisitstatetype(visitstate inState) {
  36.         if ((inState != null) && (! (inState instanceof listvisitstate)))
  37.             throw new IllegalArgumentException("Incompatable visitstate class passed");
  38.     }
  39.     
  40.     protected visitstate newvisitstate(list inList, list inState){
  41.         return new listvisitstate(inList, inState);}
  42.     protected visitstate newvisitstate(list inList){
  43.         return new listvisitstate(inList);}
  44.         
  45.     protected list newSibling() {return new list();}
  46.     protected void swapValues(list inOther) {
  47.         boolean theBool = inOther.mIsEmpty;
  48.         inOther.mIsEmpty = this.mIsEmpty;    
  49.         this.mIsEmpty = theBool;
  50.         
  51.         Object theObj = inOther.mValue;
  52.         inOther.mValue = this.mValue;        
  53.         this.mValue = theObj;
  54.         
  55.         //don't swap mRest!  we want to maintain the order of the cells
  56.     }
  57.  
  58.     public list copy() {
  59.         list newCollection = new list();
  60.         for(visitstate vs = this.initialvisitstate(); vs != null; vs = this.succeedingvisitstate(vs))
  61.             newCollection.pushend(this.elementatvisitstate(vs));
  62.         return newCollection;
  63.     }
  64.  
  65.     
  66.  
  67.     //public collection protocol stuff
  68.         
  69.     /** 
  70.      ** initialvisitstate
  71.      **/
  72.     public visitstate initialvisitstate(){
  73.         if (mIsEmpty == true) {
  74.             return null;
  75.         } else {
  76.             return newvisitstate(this);
  77.         }
  78.     }
  79.  
  80.  
  81.     /** 
  82.      ** isfinalvisitstate
  83.      **/
  84.  
  85.     public boolean isfinalvisitstate(visitstate inState){
  86.         checkvisitstatetype(inState);
  87.         if (((listvisitstate)inState).mCell.mRest == null)
  88.             return true;
  89.         else
  90.             return false;
  91.     }
  92.     
  93.     /** 
  94.      ** succeedingvisitstate
  95.      **/
  96.     public visitstate succeedingvisitstate(visitstate inState) {
  97.         checkvisitstatetype(inState);
  98.         
  99.         if (inState == null) 
  100.             throw new NullPointerException("Can't pass null visitstate.");
  101.             
  102.         if (isfinalvisitstate(inState))
  103.             return null; //    throw new collectionexception("A final visitstate has no succeeding visitstate.");
  104.             
  105.         return newvisitstate(this, ((listvisitstate)inState).mCell.mRest);
  106.     }
  107.     
  108.     
  109.     
  110.     /** 
  111.      ** elementAtvisitstate
  112.      **/
  113.     public Object elementatvisitstate(visitstate inState) {
  114.         checkvisitstatetype(inState);
  115.         if (inState != null){
  116.             return ((listvisitstate)inState).mCell.mValue;
  117.         } else {
  118.             return null;
  119.         }
  120.     }
  121.     
  122.     
  123.     
  124.     /** 
  125.      ** setelementatvisitstate
  126.      **/
  127.     public void setelementatvisitstate(visitstate inState, Object inElement) {
  128.         checkvisitstatetype(inState); 
  129.         if (inState != null){
  130.             ((listvisitstate)inState).mCell.mValue = inElement;
  131.         }
  132.     }
  133.  
  134.     
  135.     
  136.     /** 
  137.      ** removevisitstate
  138.      **/
  139.      
  140.     public void removevisitstate(visitstate inState) {
  141.         checkvisitstatetype(inState);
  142.          if ((inState != null) && (!mIsEmpty)) {
  143.              if (this == ((listvisitstate)inState).mCell) {
  144.                  //removing the first element!  What we'll actually do is set the  
  145.                  //car of the first cons cell to the car of the second, then remove
  146.                  //the second.
  147.                  if (mRest != null) {
  148.                      mValue = mRest.mValue;
  149.                      mRest = mRest.mRest;
  150.                  } else {
  151.                      mIsEmpty = true;
  152.                  }
  153.              } else {
  154.                  //scan the list then remove the baddy
  155.                  list scanner = this;
  156.                  while ((scanner.mRest != null) && (scanner.mRest != ((listvisitstate)inState).mCell)) {
  157.                      scanner = scanner.mRest;
  158.                  }
  159.                  if (scanner.mRest == ((listvisitstate)inState).mCell) {
  160.                      scanner.mRest = scanner.mRest.mRest; //remove the baddy!
  161.                  }
  162.              }
  163.          }
  164.      }
  165.      
  166.      
  167.     /** 
  168.      ** insertatvisitstate
  169.      **/
  170.     
  171.     public visitstate insertatvisitstate(visitstate inState, Object inElement) {
  172.         return this.insertatvisitstate(inState, inElement, false);
  173.     }
  174.     
  175.     public visitstate insertatvisitstate(visitstate inState, 
  176.                     Object inElement, boolean inInsertAfter){
  177.         checkvisitstatetype(inState);
  178.         listvisitstate theVS = (listvisitstate)inState;
  179.         
  180.         if (mIsEmpty) {
  181.             mValue = inElement;
  182.             mIsEmpty = false;
  183.             return newvisitstate(this);
  184.             
  185.         } else if (inState == null) {
  186.             return null; // or should we throw an error?
  187.             
  188.         } else {                                 //search the list for inState
  189.             list theNewCell;
  190.             if ((this == theVS.mCell)) {            //if inState is the first element...
  191.                 theNewCell = newSibling();                //we insert after the first element
  192.                 theNewCell.mIsEmpty = false;
  193.                 theNewCell.mValue = inElement;
  194.                 theNewCell.mRest = this.mRest;
  195.                 this.mRest = theNewCell;
  196.                 if (!inInsertAfter){                    //swap vals so the new values appear 
  197.                     this.swapValues(theNewCell);        //in front if necessary
  198.                     return newvisitstate(this);            
  199.                 } else {
  200.                     return newvisitstate(this, theNewCell);
  201.                 }
  202.                 
  203.             } else {                                //inState is not the first element
  204.                 list scanner = this;        //so we scan down the list
  205.                 while ((scanner.mRest != null) && (scanner.mRest != theVS.mCell)) {
  206.                      scanner = scanner.mRest;
  207.                 }
  208.                 if (scanner.mRest == theVS.mCell) {
  209.                     //at this point, scanner points to the cell before the one inState refers to
  210.                      if (inInsertAfter)
  211.                          scanner = scanner.mRest; 
  212.                      //now scanner points to the cell before the insertion
  213.                      theNewCell = newSibling();
  214.                     theNewCell.mIsEmpty = false;
  215.                     theNewCell.mValue = inElement;
  216.                     theNewCell.mRest = scanner.mRest;
  217.                     scanner.mRest = theNewCell;
  218.                     return newvisitstate(this, theNewCell);
  219.                 } else {
  220.                     throw new IllegalArgumentException("listvisitstate passed does not refer to this list");
  221.                 }
  222.             }
  223.         }
  224.         
  225.     }
  226.     
  227.     
  228.     public int indexatvisitstate(visitstate inState){
  229.         checkvisitstatetype(inState);
  230.         if (mIsEmpty) {
  231.             throw new RuntimeException("Cant get the index of an item from an empty list");
  232.         } else {
  233.             list scanner = this;
  234.             int i = 1;
  235.             while ((scanner != null) && (scanner != ((listvisitstate)inState).mCell)) {
  236.                  scanner = scanner.mRest;
  237.                  i++;
  238.             }
  239.             if (scanner == ((listvisitstate)inState).mCell){
  240.                 return i;
  241.             } else {
  242.                 throw new IllegalArgumentException("passed listvisitstate is not for this list");
  243.             }
  244.         }
  245.     }
  246.     
  247.         
  248.     
  249.     public visitstate visitstateatindex(int inIndex){
  250.         if (inIndex <= 0) {
  251.             throw new IndexOutOfBoundsException("collection index must be positive");
  252.         } else {
  253.             list scanner = this;
  254.             while ((scanner != null) && (inIndex-- != 1)) {
  255.                  scanner = scanner.mRest;
  256.             }
  257.             if (scanner == null){
  258.                 throw new IndexOutOfBoundsException("index is greater than length of list");
  259.             } else {
  260.                 return newvisitstate(this, scanner);;
  261.             }
  262.         }
  263.     }
  264.     
  265.     public void printOut () { //for debugging, eh
  266.         if (mValue != null){
  267.             System.out.print(mValue.toString() + ", ");
  268.         } else { 
  269.             System.out.print("null, ");
  270.         }
  271.         if (mRest != null)
  272.             mRest.printOut();
  273.     }
  274.  
  275.     public static list concatenate (list ll1, list ll2) {
  276.         list newlist = new list();
  277.         
  278.         visitstate vs;
  279.         vs = ll1.initialvisitstate();
  280.         while (vs != null) {
  281.             newlist.pushend(ll1.elementatvisitstate(vs));
  282.             vs = ll1.succeedingvisitstate(vs);
  283.         }
  284.         vs = ll2.initialvisitstate();
  285.         while (vs != null) {
  286.             newlist.pushend(ll2.elementatvisitstate(vs));
  287.             vs = ll2.succeedingvisitstate(vs);
  288.         }
  289.         
  290.         return newlist;
  291.     }
  292.  
  293. //helpers
  294. //Added by AP 8/14
  295.     public list rest() {
  296.         return mRest;
  297.     }
  298.     
  299.     public list reverse() {
  300.         list outlist = new list();
  301.         visitstate vs;
  302.         vs = this.initialvisitstate();
  303.         while (vs != null) {
  304.             outlist.push(this.elementatvisitstate(vs));
  305.             vs = this.succeedingvisitstate(vs);
  306.         }
  307.     return outlist;
  308.     }
  309.     
  310.     
  311. }